package com.example.demo.basics.arit;

/**
 * @author aqua
 * @description 二叉树
 * 特点：左边小于根  右边大于根  内饰二分查找
 * 时间复杂度o(logn)
 * 中序便利：左根（输出）右
 * 查询次数有几层插几次 20亿个节点查 2^32=21亿 32次
 * 缺点： 容易劈腿 第一次插入0直接劈腿 时间复杂度位o(n)
 *
 * 二叉树平衡树 左右子树高度相差不超过1 这样可避免劈腿 理想状态只出现在实验不适合业务
 *
 * 思路：定义数据结构left right  存入num数字
 *添加  判断如果我传进来的值大于根节点 采用递归添加到右反左 添加采用递归
 *
 * @date 2020年11月03 1:19
 * @email 1301584033@qq.com
 */
public class BinarySearchTree {
        int num; //数字
    BinarySearchTree left;
    BinarySearchTree right;

    public BinarySearchTree(int num) {
        this.num = num;
        this.left = null;
        this.right = null;
    }
    //插入
   public void insert(BinarySearchTree root,int num){
        //如果我传进来的值大于根节点
        if(root.num<num){
            //插入右边
            if(root.right==null){
                root.right=new BinarySearchTree(num);
            }else{
                insert(root.right,num);
            }
        }else {
            //插入左边
            if(root.left==null){
                root.left=new BinarySearchTree(num);
            }else{
                insert(root.left,num);
            }
        }

   }
   //中序遍历
    public void inOrder(BinarySearchTree root){
        //找到最后一个左边输出 在输出右边 在回来
        if(root!=null){
            inOrder(root.left);
            System.out.println(root.num);
            inOrder(root.right);
        }

    }
    //升序遍历
    public void indownOrder(BinarySearchTree root){
        if(root!=null){
            indownOrder(root.right);
            System.out.println(root.num);
            indownOrder(root.left);
        }

    }

    public static void main(String[] args) {
        int data[]={10,9,0,3,5,7,77,6,4,2,1};
        //实例化一个节点
        BinarySearchTree binarySearchTree=new BinarySearchTree(data[0]);
        for (int i=1;i<data.length;i++){
            binarySearchTree.insert(binarySearchTree,data[i]);

        }
        System.out.println("中序遍历");
        binarySearchTree.inOrder(binarySearchTree);
        System.out.println("倒序");
        binarySearchTree.indownOrder(binarySearchTree);
    }


}
